package day0313

import (
	"math"
	"sort"
)

func threeSumClosest(nums []int, target int) (ans int) {
	n := len(nums)
	sort.Ints(nums)
	minVal := math.MaxInt64
	for i := 0; i < n; i++ {
		left, right := i+1, n-1
		for left < right {
			t := nums[i] + nums[left] + nums[right] - target
			if abs(t) < minVal {
				minVal = abs(t)
				ans = nums[i] + nums[left] + nums[right]
			}
			if t > 0 {
				right--
			} else if t < 0 {
				left++
			} else {
				return target
			}
		}
	}
	return
}

func abs(x int) int {
	if x < 0 {
		return -x
	}
	return x
}
